package xyz.scootaloo.adt.tree

import org.junit.Test

/**
 * 基于Java版, 重新设计得到的Kotlin版本
 *
 * @author flutterdash@qq.com
 * @since 2021/4/20 12:02
 */
class TrieTree {
    /** [root] 根节点 */
    private val root = LetterNode('*')
    private val pathRecord = ArrayDeque<LetterNode>()

    fun add(word: String) {
        searchNode(word)
    }

    fun contains(word: String): Boolean {
        return searchNode(word, false) { node, _ ->
            node.isEndpoint
        }
    }

    @Deprecated("暂不支持删除功能")
    fun remove(word: String) {
        if (word.isEmpty())
            return
        searchNode(word, collectPath = true) { _, path ->
            var current = path.removeLast()
            if (current.isEndpoint) {
                current.isEndpoint = false
            }

            while (path.size > 1) {
                current = path.removeLast()
                if (current.nextTab != null && current.nextTab!!.size == 1) {
                    current.nextTab = null
                }
            }

            path.clear()
            return
        }
    }

    private inline fun searchNode(
        word: String,
        createOnMissing: Boolean = true,
        collectPath: Boolean = false,
        action: (node: LetterNode, path: ArrayDeque<LetterNode>) -> Boolean = { _, _ -> true }
    ): Boolean {

        var node = root
        for (char in word) {
            var nextNode = node.gotoNextNode(char)
            if (nextNode == null) {
                if (createOnMissing)
                    nextNode = node.addSubNode(char)
                else
                    return false
            }

            if (collectPath) {
                pathRecord.addLast(nextNode)
            }

            node = nextNode
        }
        if (createOnMissing)
            node.isEndpoint = true
        return action(node, pathRecord)
    }

    private class LetterNode(_letter_: Char) {
        /**
         * [isEndpoint] 是否有以此结尾的单词
         * [nextTab]    此位置为前缀的其他单词
         */
        val key: Int = _letter_.toInt()
        var isEndpoint: Boolean = false
        var nextTab: MutableList<LetterNode>? = null


        fun addSubNode(char: Char): LetterNode {
            val newNode = gotoNextNode(char) ?: LetterNode(char)
            if (nextTab == null) {
                nextTab = mutableListOf(newNode)
                return newNode
            }

            val intValue = char.toInt()
            if (nextTab!![0].key > intValue) {
                nextTab!!.add(0, newNode)
            } else if (nextTab!![nextTab!!.size - 1].key < intValue) {
                nextTab!!.add(newNode)
            } else {
                for (idx in 1 until (nextTab!!.size)) {
                    if (nextTab!![idx].key > intValue && nextTab!![idx - 1].key < intValue) {
                        nextTab!!.add(idx, newNode)
                        break
                    }
                }
            }

            return newNode
        }

        fun gotoNextNode(char: Char): LetterNode? {
            if (nextTab == null)
                return null
            val index = binarySearch(char)
            if (index < 0)
                return null
            return nextTab!![index]
        }

        @Deprecated("")
        fun removeSubNode(char: Char) {
            val index = binarySearch(char)
            if (index < 0)
                return
            nextTab!!.removeAt(index)
        }

        private fun binarySearch(char: Char): Int {
            val intValue = char.toInt()
            return nextTab!!.binarySearch {
                it.key - intValue
            }
        }

        override fun equals(other: Any?): Boolean {
            if (this === other) return true
            if (javaClass != other?.javaClass) return false

            other as LetterNode

            if (key != other.key) return false

            return true
        }

        override fun hashCode(): Int {
            return key
        }

        override fun toString(): String {
            return "LetterNode(key=${key.toChar()}, isEndpoint=$isEndpoint)"
        }

    }

}
